package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 快速排序
 * 通过递归实现
 * -8 100 9 0 45 -19 2
 * 找一个中间点 比如 0 然后将比0 大的放右边 比0 小的放左边（0可能会随着排序过程中变换位置）
 *  如何将比0 小的放左边？比0 大的放右边？
 *      这里注意：不是将0 作为数组的中间 不要考虑左右数据个数不等的问题。这里0 这个数据只是一个参照物 并且0 的位置在程序执行过程中是会改变的
 *      全表扫描 找比0 大的  全表扫描 找比0 小的
 *
 *      1）从左边往右边一直扫描，直到扫描到一个比0 大或等于的值 索引left
 *      2）从右边往左边一直扫描，直到扫描到一个比0 小或等于的值 索引right
 *      3）如果left >= right 说明已经达到这个效果了
 *      4）否则 就进行left 和 right 索引位置的值替换
 *      5）替换后 如果left索引位置的值=0  就将right--
 *            如果right索引位置的值=0 就将left--
 *      如此往复上面的操作
 *                                       -8 100 9 0 45 -19 2 10 我们以10 为标准
 *  left=0  指向-1 执行1 得到-》left=1 指向100
 *  right=7 指向10 执行2 得到-》right=7 指向10
 *  执行3 不满足 执行4  得到                                 -8 10 9 0 45 -19 2 100
 *  执行5 得到 left=1 指向10 执行1 得到-》 left=1 指向10
 *           right=6 指向2 执行2 得到-》 right=6 指向2
 *  执行3 不满足 执行4 得到                                  -8 2 9 0 45 -19 10 100
 *  执行5 得到 left=2 指向9 执行1 得到-》left=4 指向45
 *           right=6 指向10 执行2 得到-》right=6 指向10
 *  执行3 不满足 执行4 得到                                  -8 2 9 0 10 -19 45 100
 *  执行5 得到left=4 指向10 执行1 得到-》 left=4 指向10
 *          right=5 指向-19 执行2 得到-》 right=5 指向-19
 *  执行3 不满足 执行4 得到                                  -8 2 9 0 -19 10 45 100
 *  执行5 得到left=5 指向10
 *          right=4 指向-19
 *  执行3 说明这个已经满足了10 左边的数据比10小 右边的数据比10 大
 *
 *
 *
 * 然后再将数据 分成0 的左边和右边 对左边 和右边分别进行上面一步
 */
public class QuickSort {

    public static void main(String[] args) {

        int size = 8;
        int[] testArr = new int[size];
        for (int i = 0; i < testArr.length; i++) {
            testArr[i] = (int) (Math.random() * size);
        }
        System.out.println(Arrays.toString(testArr));
        Instant start = Instant.now();
        // quickSort(testArr,0,size-1);
        // partition(testArr,0,size-1);
        partitionTwo(testArr, 0, size - 1);
        Instant end = Instant.now();
        System.out.println(Duration.between(start, end).toMillis()); //50
        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 快速排序
     * @param arr
     * @param start
     * @param end
     */
    public static void quickSort(int[] arr,int start ,int end ) {
        int left=start,right=end,midValue=arr[(left+right)/2];

        int temp;
        while (left<right){
            // 从左边第一个开始找  找到大于等于 中间值的数据
            while (arr[left]<midValue){
                left++;
            }
            // 从右边第一个开始找  找到小于等于 中间值的数据
            while (arr[right]>midValue){
                right--;
            }
            if(left>=right){// 这个时候说明 已经实现了 一段是比中间值小 一段比中间值大 不需要交换了
                break;
            }
            // 交换
            temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;

            // 如果替换后 left 位置的值 = midValue 就需要讲right-1  因为left索引位置的值还需要进行比较
            if(arr[left]==midValue){
                right--;
            }

            if(arr[right]==midValue){
                left++;
            }
        }
        if(left==right){    // 为了结束循环
            left++;
            right--;
        }
        // 左递归
        if (start < right) {
            quickSort(arr, start, right);
        }
        // 右递归
        //
        if (left < end) {
            quickSort(arr, left, end);
        }
    }

    /**
     * 单边循环
     * 5 3 7 2 9 8 1 4
     * 1、选择最右元素作为基准点元素
     * 2、j指针负责从左向右遍历找到比基准点小的元素，一旦找到则与i指针元素交换。
     * 3、i指针维护小于基准点元素的边界，也是每次交换的目标索引
     * 4、最后基准点与i交换，i即为中间元素，左边元素都比i小，右边元素都比i大。
     * <p>
     * 最开始 基准元素4 i j 索引为0
     * 第一轮比较 5 比 4 大不动，j+1
     * 第二轮比较 3 比 4 小 与i交换，i+1 ,j+1
     * 3 5 7 2 9 8 1 4
     * 第三轮比较 7 比 4 大不动，j+1
     * 第四轮比较 2 比 4 小 与i交换，i+1 ,j+1
     * 3 2 7 5 9 8 1 4
     * 第五轮比较 9 比 4 大不动，j+1
     * 第六轮比较 8 比 4 大不动，j+1
     * 第七轮比较 1 比 4 小与i交换，i+1 ,j+1
     * 3 2 1 5 9 8 7 4
     * 最后将 i 与 j 位置交换
     * 3 2 1 4 9 8 7 5
     * 得到的数组，就是4左边比4小，4右边比4大。
     * <p>
     * 然后将4左边或4 右边分别当做数组执行上面逻辑
     *
     * @param arr 数组
     * @param l   左边界
     * @param r   右边界
     */
    public static void partition(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l, j = l;
        while (j < r) {
            if (arr[j] < arr[r]) {
                // 交换i 和 j 元素，同时 i  j  都加1
                swap(arr, i++, j++);
            } else {
                j++;
            }
        }
        // 最后交换i 和 j 的位置。
        swap(arr, j, i);
        // 递归往下
        partition(arr, l, i - 1);
        partition(arr, i + 1, r);
    }

    public static void swap(int[] arr, int a, int b) {
        if (a == b) {
            return;
        }
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 双边循环
     * 1、选择最左边元素作为基准点元素。
     * 2、j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦i j 都找到了就交换，直到i+1=j（需要判断交换）(必须先j找，后i找)
     * 3、最后基准点与i所在位置交换，i即为分区位置
     * 5 3 7 2 9 8 1 4
     * 最开始基准元素为5，i=0 ,j=7
     * j 从右向右找比5小的元素，4 。i从左向右找比5大的元素，7.两者交换
     * 5 3 4 2 9 8 1 7
     */
    public static void partitionTwo(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int base = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            // 必须先j找，后i找
            // j 从右向左找小的
            while (i < j && arr[j] > base) {
                j--;
            }
            // i 从左向右找大的
            while (i < j && arr[i] <= base) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, l, j);

        // 递归往下
        partitionTwo(arr, l, j - 1);
        partitionTwo(arr, j + 1, r);
    }
}
